package chapter2;

/**
 * 循环删除第m个节点
 */
public class JosepushKill {
    /**
     * 循环删除第m个节点，循环使用一个head指针一个last指针
     * last.next = head.next;
     * 复杂度O(n*m)
     * @param head
     * @param m
     * @return
     */
    public ListNode josepushKill(ListNode head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }
        ListNode last = head;
        while (last.next != head) {
            last = last.next;
        }
        int count = 0;
        while (head != last) {
            if (++count == m) {
                last.next = head.next;
            } else {
                last = last.next;
            }
            head = head.next;
        }
        return head;
    }

    public ListNode josepushKill2(ListNode head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }
        ListNode current = head.next;
        int tmp = 1;// list size
        while (current != head) {
            tmp++;
            current = current.next;
        }
        tmp = getLive(tmp, m);//生存节点编号
        while (--tmp != 0) {
            head = head.next;
        }
        head.next = head; // 生存的唯一节点
        return head;
    }

    /**
     * O(N)
     * @param i
     * @param m
     * @return
     */
    private int getLive(int i, int m) {
        if (i == 1) return i;
        return (getLive(i - 1, m) + m - 1) % i + 1;
    }
}
